package com.leetcode;

/**
 * 35. 搜索插入位置
 * 递归法
 *
 * @author fy
 * @date 2022/4/18 21:40
 */
public class Solution35 {

    public int searchInsert(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }

    private int binarySearch(int[] nums, int target, int start, int end) {
        if (start > end) {
            return start;
        }
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        return binarySearch(nums, target, start, end);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,3,5,6};
        int target = 7;
        int res = new Solution35().searchInsert(nums, target);
        System.out.println(res);
    }

}
